#! -*- encoding=utf-8 -*-
"""
使用双向链表实现LRU(最近最少使用算法)，每次使用把使用的节点放到链表的最前面，
淘汰缓存时只需要将尾部结点淘汰即可
"""
from computer_sience import DoubleLinkList, Node


class LRUCache(object):

    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}  # 保存key和结点的映射关系
        self.list = DoubleLinkList(self.capacity)

    def get(self, key):
        if key in self.map:  # 该节点在缓存中，就将该节点取出并从内存中删除，同时将其添加到缓存头部
            node = self.map[key]
            self.list.remove(node)
            self.list.append_front(node)
            return node.value
        else:
            return -1

    def put(self, key, value):
        if key in self.map:  # 如果要添加的结点在缓存中，就将旧的结点取出并删除，将旧结点value重新赋值，同时接到缓存头部
            node = self.map.get(key)
            self.list.remove(node)
            node.value = value
            self.list.append_front(node)
        else:  # key 不在缓存中
            node = Node(key, value)

            # 缓存已满, 需要将缓存中尾部结点淘汰，
            if self.list.size >= self.list.capacity:
                old_node = self.list.remove()
                self.map.pop(old_node.key)

            # 缓存未满，直接将结点接到缓存头部，同时将node和key映射保存到本地map
            self.list.append_front(node)
            self.map[key] = node

    def print(self):
        self.list.print()

if __name__ == '__main__' :
    cache = LRUCache(2)
    cache.put(2, 2)
    cache.print()
    cache.put(1, 1)
    cache.print()
    cache.put(3, 3)
    cache.print()
    print(cache.get(1))
    cache.print()
    print(cache.get(2))
    cache.print()
    print(cache.get(3))
    cache.print()
